Sorting Algorithms (Again)

Merge Sort

if only one number # (base case)
    quit
else
    sort left half of numbers
    sort right half of numbers
    merge sorted halves

• Merge sort uses more memory.
• \Theta(n\log n)